package tree.serialize;

import java.util.ArrayList;
import java.util.List;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */
public class SerializeTree {

    public static void main(String[] args) {
        //1,2,3,null,null,4,5
        TreeNode treeNode = new TreeNode(1);
        treeNode.left = new TreeNode(2);
        treeNode.right = new TreeNode(3);
        treeNode.right.left = new TreeNode(4);
        treeNode.right.right = new TreeNode(5);

        String serializeStr = serialize(treeNode);
        System.out.println(serializeStr);

        TreeNode ret = deserialize(serializeStr);
        System.out.println(ret);
    }

    // Encodes a tree to a single string.
    static String serialize(TreeNode root) {

        if (root == null) {
            return "[]";
        }
        List<TreeNode> list = new ArrayList<TreeNode>();
        list.add(root);
        // [1,2,3,null,null,4,5]
        for (int i = 0; i < list.size(); i++) {
            TreeNode node = list.get(i);
            if (node == null) {
                continue;
            }
            list.add(node.left);
            list.add(node.right);
        }

        //[1,2,3,null,null,4,5]
        while (list.get(list.size() - 1) == null) {
            list.remove(list.size() - 1);
        }

        StringBuilder sb = new StringBuilder("[");
        sb.append(list.get(0).val);

        for (int i = 1; i < list.size(); i++) {
            if (list.get(i) == null) {
                sb.append(",null");
            } else {
                sb.append("," + list.get(i).val);
            }
        }
        sb.append("]");
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    static TreeNode deserialize(String data) {

        if (data == null || data.equals("[]")) {
            return null;
        }

        //1,2,3,null,null,4,5
        String[] datas = data.substring(1, data.length() - 1).split(",");
        boolean isLeft = true;
        TreeNode node = new TreeNode(Integer.parseInt(datas[0]));
        List<TreeNode> list = new ArrayList<TreeNode>();
        list.add(node);
        int index = 0;
        for (int i = 1; i < datas.length; i++) {
            if (!datas[i].equals("null")) {
                TreeNode node1 = new TreeNode(Integer.parseInt(datas[i]));
                if (isLeft) {
                    list.get(index).left = node1;
                } else {
                    list.get(index).right = node1;
                }
                list.add(node1);
            }

            if (!isLeft) {
                index++;
            }

            isLeft = !isLeft;
        }
        return list.get(0);
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }

}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));
//分析： 1. 考查树存储结构       -----> 用List<TreeNode> 存储带有子节点的各节点
//      2. 遍历、取值